In areas having little or no infrastructure for telecommunication, and in areas where telecommunication using the infrastructure is too expensive, users of wireless mobile stations may still be able to communicate with each other through the formation of an ad hoc network. Generally, in such a network each mobile station operates not only as a host but also as a router, forwarding packets to other mobile stations in the ad hoc network that may not be within direct wireless transmission range of each other Each node uses an ad hoc routing protocol that allows it to discover “multi-hop” paths through the network formed to any other node. Mobile stations in these networks establish routing among themselves to form their own network “on the fly”.
Possible uses for such networks, called Mobile Ad Hoc Networks (MANETs), include e.g. business associates sharing information during a meeting, soldiers relaying information on the battlefield, and emergency relief personnel who must quickly set up a network to coordinate efforts after a hurricane or an earthquake. A particular application which will probably introduce ad hoc networking to the mass market involves the use of devices working according to the standard Bluetooth, a standard for allowing low-power short range radio communication and initially intended as a means to replace cables.
Such mobile ad hoc networks have been studied for some time, but most work has been concentrated on stand-alone ad hoc networks. Several proposed routing protocols use reactive routing, also known as on-demand routing as opposed to ordinary Internet Protocol (“IP”) routing, which uses proactive routing. Proactive routing means that the routing protocol constantly tries to keep track of the routes in the network so that when a host needs to send a datagram a route to the recipient is known beforehand. Reactive routing means that the routing protocol only operates when there are datagrams to deliver in the network, otherwise it does nothing.
There are two basic problems with the mobile ad hoc networks:                How can someone connect an ad hoc network that uses on-demand routing to the Internet?        How can Mobile IP services be connected in such an ad hoc network?        
Addressing in the Internet is hierarchical with IP addresses divided into a network ID and a host ID. All hosts connected to the same network use the same network ID. In this way, each IP address is mapped to a physical location that can be derived by looking at the network ID of the IP address. This also means that an Internet host does not have to keep track of routes to every other Internet host. Instead, routing information can be aggregated; one entry in the routing table can handle all hosts that share the same network ID. To make better use of the address space, yet another level of hierarchy is used: a network can be divided into subnetworks. The host ID is then divided into a subnet ID and a host ID.
The number of networks in the Internet is quite substantial and it is not always necessary to keep track of them all, since they only have limited interconnections. Because most networks are leaf networks, default routes are widely used. In short, IP routing works as follows:    1. Look for an entry in the routing table that matches the complete destination IP address. If found, use that route.    2. Look for an entry in the routing table that matches the network ID of the destination IP address. If found, use that route.    3. Look for a default entry in the routing table. If found use that route, otherwise consider the destination unreachable.
The capability of using one route to a network instead of having one route per host and using a default route is two powerful features of IP routing.
If someone wants an ad hoc network to be routable from the Internet like any other Internet network, someone must assign a network ID thereto and ensure that the nodes in the ad hoc network use it. If such a method is used, the IP multihop communication within the ad hoc network is what distinguishes it from regular Internet networks. Nodes in the ad hoc network cannot expect to have link-layer connectivity with all other nodes in the ad hoc network as in regular Internet networks. In order to reach the default gateway between the ad hoc network and the fixed Internet, nodes must use IP layer routing.
The traditional view of ad hoc networks is as autonomous systems of mobile nodes using IP. As such, the ad hoc network should be capable of operating without any centralized configuration. Also, from an ad hoc point of view, any set of nodes should be capable of forming an ad hoc network regardless of the addresses which they use and without having to use any particular network ID. This implies that one can no longer decide if a node belongs to that particular network simply by looking at the network ID.
In the following the focus will be on what happens when such an autonomous ad hoc network is connected to the Internet and the nodes within the ad hoc network wish to communicate with other Internet hosts.
Most work concerning routing in ad hoc networks has been concentrated on stand-alone ad hoc networks. The IP mobility that is provided in earlier ad hoc networks was limited to the ad hoc network as such. To allow roaming between different networks the Mobile IP protocol was developed, separately from ad hoc networking. In a stand-alone ad hoc network, without the hierarchy that the network ID creates, there is no meaning in having a default route since either the recipient is reachable within the ad hoc network or it is not reachable at all. As a result thereof, routing in ad hoc networks is typically performed using host routes only.
This is the case for both Ad Hoc On-demand Distance Vector Routing (“AODV”) and Dynamic Source Routing (“DSR”) for example, which use neither network nor default routes. In AODV there are no periodic changes of the routing tables. Routes are only set up when two nodes want to communicate with each other, and only nodes that are connected in the path between the two end nodes keep information about the route. In the AODV method: (a) discovery packets are broadcast as sparingly as possible; (b) is distinguished between local connectivity management and general topology maintenance; and (c) information is propagated about changes in local connectivity to neighbouring nodes which are likely to need that information. One key aspect of AODV is that each node maintains a routing table containing one entry for each destination with which the node communicates itself or to or from which the node forwards data to on behalf of some other node.
Another type of known on-demand routing is DSR. The feature that makes DSR stand out from other routing protocols of Mobile Ad Hoc Networks is that DSR uses strict source routing. Strict source routing means that the source determines the complete sequence of hops that each packet should traverse. The list of hops is then included in the header of each packet. One obvious disadvantage thereof is the source routing overhead which every packet has to carry. Loose source routing is a method according to which a packet must be routed via some specific nodes, e.g. a foreign agent in this case, but otherwise can choose its own way to the destination.
In DSR two basic mechanisms are used, route discovery and route maintenance. Route maintenance is used for handling link breakages and is carried out whenever a route is used to send packets. Route discovery is used to find a route from the source to the destination. The network is flooded with route request messages. Each node in the network adds its address to a route request received in the node and then forwards it. If a route exists to the destination the route request will find its way to the destination. All that the destination node has to do is unicast a route reply back to the source using the route listed in the route request. Each node in the network maintains a route memory in which it stores the routes that it has learned. Route discovery is only used when an appropriate route cannot be found in the route memory.
In on-demand routing methods like DSR and AODV the routing tables are usually searched in the following manner:    1. Look for an entry in the routing table that matches the complete destination IP address. If found, use that route.    2. Try to find a host route within the ad hoc network by using the route discovery mechanisms. If found, use that route, otherwise consider the destination unreachable.
Host routing by nodes in an ad hoc network as described above should be feasible for destinations on the fixed Internet when an ad hoc network is connected to the fixed Internet since routing information is only kept for destinations with which an ad hoc node is currently communicating. What is lacking in these procedures is a mechanism for propagating routing information from the fixed Internet to the ad hoc network, i.e. how nodes in the ad hoc network should treat network and default routes.
To be reachable from the rest of the Internet, a node in an ad hoc network needs an IP address that allows the ad hoc node to be routable from the rest of the Internet. Since the ad hoc network is connected to the Internet there must be at least one node that resides on the border between the ad hoc network and the rest of the Internet. This node will be referred to as the Internet gateway. The Internet gateway must have at least one IP address that can be used for communication with the rest of the Internet. How can the nodes in the ad hoc network make use of that fact?
Mobile IP is a proposed standard protocol for location independent routing. It allows a mobile node to have seamless, untethered access to the Internet while roaming and is based on the Internet Protocol by making mobility transparent to applications and higher level protocols like TCP and UDP. The main technical obstacle that had to be overcome to support mobility was the way in which the IP addresses are used. Unicast Internet traffic is routed to the location specified by the destination address in the IP header. The address specifies a network address and hence traffic is sent to this network.
Unfortunately this does not work for mobile nodes since a mobile node wants to have the same address independently of its location without the sender having to keep track of the place where the mobile node is located. Mobile IP solved this problem by allowing the mobile node to use two IP addresses, one for identification by e.g. TCP, and one for routing to the current location of the node.
In order to maintain existing transport layer connections every mobile node is assigned a static home address. This home address allows the mobile node to always be capable of receiving data in the same way as it receives data in its home network. When the mobile node is attached to a network different from its home network, called a foreign network, it uses a care-of address. The care-of address is an IP address valid in the foreign network that the mobile node is visiting. Whenever a mobile node moves from one network to another it has to change to a new care-of address that is valid in the new network.
To be capable of receiving datagrams while visiting a foreign network the mobile node has to register its current care-of address with its home agent. To do this, the mobile node usually has to register through a foreign agent FA located in the foreign network. The process of detecting a foreign agent is quite similar to that used by Internet nodes to detect routers which support the Internet Control Message Protocol (ICMP). Each mobility agent periodically broadcasts agent advertisements to its directly attached subnetworks to advertise its existence. The mobile node listens for these advertisements in order to select a mobility agent, i.e. a foreign agent, through which the node can register with its home agent.
When the node is successfully registered with the home agent, every datagram sent to the home address of the mobile node is received by the home agent and forwarded to the care-of address, e.g. the foreign agent, that then forwards it to the mobile node. The forwarding is performed using a method called tunnelling. When the home agent receives a datagram destined for the mobile node, it encapsulates the original datagram within a new IP packet that contains the care-of address of the mobile node as its destination address. This new IP packet is then routed to the care-of address where it is then decapsulated. The decapsulated packet is now said to have been tunnelled. If the care-of address is the care-of address of a foreign agent the foreign agent forwards the decapsulated datagram to the mobile node.
The procedure used by ordinary Mobile IP with foreign agent care-of addresses assumes link-layer connectivity between the foreign agent and the visiting node In summary, the communication between foreign agents and visiting nodes is as follows:    1. Foreign agents broadcast agent advertisements periodically, once per second. These advertisements are used by visiting nodes to            detect the presence of a foreign agent        discover the presence of new foreign agents,        decide when it has moved, and        detect when a foreign agent is no longer reachable.            2. Visiting nodes may broadcast agent solicitations to detect foreign agents. A foreign agent that receives an agent solicitation must respond by sending a unicast agent advertisement.    3. When a visiting node has received a valid agent advertisement from a foreign agent it may register with that foreign agent.
IP broadcast messages are used frequently for the operation of ordinary Mobile IP. In ad hoc networks, such broadcast messages are much more costly, since they have to traverse multiple hops and must be retransmitted by every node within the ad hoc network. Thus, it would be desirable to reduce the number of broadcast messages if possible.
Some methods already exist which attempt to apply Mobile IP to ad hoc networks. In “Ad Hoc Networking with Mobile IP”, Proceedings of 2nd European Personal Mobile Communication Conference, September 1997, a solution for using Mobile IP on top of a proactive routing protocol is described. The routing protocol that is used is said to be “a modified RIP”, and is very similar to Destination Sequenced Distance Vector Routing (“DSDV”). It seems fairly straightforward to use the proposed method for a proactive routing protocol like DSDV, but it is not viable for a reactive, on-demand, routing protocol since it relies on periodically transmitted control packets of the routing protocol for spreading Agent Advertisements. In an on-demand routing protocol, there is no such thing as periodically transmitted control packets.
One point made in the cited “Ad Hoc Networking” article is that both Mobile IP and the ad hoc routing protocol use routing tables. To coordinate the two routing tables, a route manager is introduced. Instead of modifying the routing table directly, both Mobile IP and the ad hoc routing protocol send their route manipulation requests to the route manager. It is then up to the route manager to determined those manipulations that should be carried out.
For combining Mobile IP with ad hoc networks using on-demand routing protocols, no detailed solution has been disclosed. In “Supporting Hierarchy and Heterogeneous Interfaces in Multi-Hop Wireless Ad Hoc Networks”, Proceedings of the Workshop on Mobile Computing, IEEE, June 1999, an initial design of an addressing architecture is described which, among other things, could be used to provide Mobile IP support within an ad hoc network. The section that covers interworking between Mobile IP and ad hoc networking is, however, not very elaborate. Additionally, it assumes that DSR is used as the routing protocol in the ad hoc network.
However the procedure of “Supporting Hierarchy” according to the cited article only considers one foreign agent and one mobile node only. The idea comprises that the mobile node piggybacks a Mobile IP Agent Solicitation on a Route Request targeting the IP limited broadcast address (255.255.255.255). The limited broadcast is used to allow the Solicitation to propagate over multiple hops through the ad hoc network, but not be forwarded to the Internet by gateways. When the foreign agent receives the Solicitation, it will unicast an Agent Advertisement in reply. Once the Agent Advertisement reaches the mobile node, the mobile node can register with the foreign agent and the ordinary triangle routing of Mobile IP can begin.
A basic problem when using Mobile IP in a Mobile Ad Hoc Network is that link-layer connectivity between the foreign agent and the mobile node cannot be assumed. In the first solution disclosed in the cited “Ad Hoc Networking” on-demand routing is not used and is thus not applicable.
The shortcomings of the second solution described above in the cited article “Supporting Hierarchy” are:    1. It assumes that DSR is used.    2. There is no movement detection or handoff support.    3. It uses a special addressing scheme with interface index.
Accordingly, there exists a need for a mobile ad hoc network which can communicate with the Internet using Mobile IP foreign agents as gateways which uses on-demand routing but does not require a specific ad hoc routing protocol used in the ad hoc network, nor link-layer connectivity between foreign agent and visiting node, and allows movement detection and handoff support.